package com.frx.sort.heap;

import java.util.Arrays;

/**
 * @author ：frx
 * @date ：Created in 2019/11/12 22:05
 * @description：ToDO
 * @modified By：
 * @version: ToDO
 */
public class HeapSort {

    public static void main(String[] args){
        int[] arr = {3,1,2,4,6,5};
        sortHeap(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sortHeap(int[] arr){
        //1.建堆
        buildHeap(arr);
        System.out.println(Arrays.toString(arr));
        // 2.排序 先交换堆顶和数组尾部的两个元素的值，然后下沉堆化
        int k = arr.length-1;
        while (k>0){
            int tmp = arr[k];
            arr[k] = arr[0];
            arr[0] = tmp;
            k--;
            siftdown(arr,0,k);
        }
    }

    private static void buildHeap(int[] arr){
        int len = arr.length-1;
        for (int n = (len-1)/2;n>=0;n--){
            siftdown(arr,n,arr.length);
        }
    }

    /**
     * 堆的下沉操作
     */
    private static void siftdown(int[] arr,int n,int len){
        while (true){
            int maxIndex = n;
            if (2*n + 1 < len && arr[2*n+1] > arr[n]){
                maxIndex = 2*n + 1;
            }
            if (2*n+2<len&&arr[2*n+2]>arr[maxIndex]){
                maxIndex = 2*n+2;
            }
            if (n==maxIndex){
                break;
            }
            int tmp = arr[maxIndex];
            arr[maxIndex] = arr[n];
            arr[n] = tmp;
            n = maxIndex;

        }
    }



}
